package com.guaoran.algorithm.two.pointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Auth gucheng
 * @Desc 获取 a + b + c = 0 的元素
 * https://leetcode.com/problems/3sum/
 * @Date 2021/1/8 下午5:07
 */
public class ThreeSum {
    public static void main(String[] args) {
        System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    }
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if(nums == null || nums.length == 0){
            return result;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length ; i++) {
            // 忽略第一个比较的值存在重复的记录
            if(i>0 && nums[i] == nums[i-1]){
                continue;
            }
            int start = i+1;
            int end = nums.length -1;
            while(start <end){
                if(nums[i]+nums[start]+nums[end]==0){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[start]);
                    list.add(nums[end]);
                    result.add(list);
                    start++;
                    end --;
                    while (start<end && nums[start] == nums[start -1]){
                        start++;
                    }
                    while (start<end && nums[end] == nums[end+1]){
                        end --;
                    }
                } else if (nums[i] + nums[start] + nums[end] >0) {
                    end --;
                } else{
                    start ++;
                }
            }
        }
        return result;
    }
}
